/* *
* 时间复杂度为 O(n^2) 空间复杂度为 O(1) 稳定
* 插入排序的基本思想是将数组分成已排序和未排序两个部分，每次从未排序部分取出一个元素插入到已排序部分的正确位置。在插入过程中，需要不断地比较已排序部分的元素，找到插入位置，然后将该位置之后的元素后移一位，为新元素腾出位置
* */


function insertSort(arr) {

    for (let i = 1; i < arr.length; i ++) {
        const num = arr[i]
        let j = i - 1
        while (j >= 0 && num < arr[j]) {
            arr[j + 1] = arr[j]
            j--
        }
        arr[j + 1] = num
    }
    return arr

}
const arr = [5,2,6,1,7,2,10,8]
console.log(insertSort(arr));
